package reviewAlgorithms.binarySearch;

public class NextGreatestLetter {
    public static void main(String[] args) {
        String str = "eeennn";
        char target = 'e';
        System.out.println(nextGreatestLetter(str.toCharArray(),target));
    }
    public static char nextGreatestLetter(char[] letters, char target) {
        if (letters == null || letters.length < 1) {
            return '?';
        }
        int left = 0;
        int right = letters.length - 1;
        int center;
        int ans = -1;
        while (left <= right){
            center = (right + left)/2;
            if (letters[center] < target){
                left = center + 1;
            }else if (letters[center] >= target){
                ans = center;
                right = center - 1;
            }
        }
        if (ans == -1){
            return letters[0];
        }else if (letters[ans] == target){
            while (ans + 1 < letters.length && letters[ans + 1] == target){
                ans += 1;
            }
            if (ans + 1 < letters.length){
                return letters[ans + 1];
            }else {
                return letters[0];
            }
        }else {
            return letters[ans];
        }
    }
}
